/************************************
 *	mmu.cc							*
 *	Added in Project3				*
 *	By OceanMaster					*
 ************************************/
#ifdef USE_TLB
#include "mmu.h"
#include <map>
#include <stdlib.h>
#define R_MAX 2147483647	//buggest possible number returned of rand();

using namespace std;

OpenFile * SwapFile;				//Swap File handler
BitMap * SwapFileMap;				//The bit map to store position indexes in swap file
Lock * SwapLock;
bool useFIFO;

Lock * tmpLock;
int nextTLBEntry;					//the entry to be replaced on next TLB miss
int lastProcessId;					//processId of last process that using TLB table
InvertedTranslationEntry * ipt;	//Inverted Page Table
map<int,int>	hash;				//hash table for ipt
Lock * IPTLock;

List * queue;

//char * memory;
/***************************
 *	Utility				   *
 ***************************/


/***************************
 *	MMU init and finalize  *
 ***************************/
void initMMU()				//Initialize Varible
{
	DEBUG('3',"Initialize Varibles needed in Memory Management Unit\n");
	
	SwapFileMap = new BitMap(SwapFilePages);

	fileSystem -> Create("Group11SwapFile",SwapFilePages*PageSize);
	SwapFile = fileSystem -> Open("Group11SwapFile");
	//memory = new char[SwapFilePages*PageSize];

	if(SwapFile == NULL)	//if swap file doesn't exist 
	{
 		printf("FATAL ERROR : Swap File Cannot be created.\n");
		interrupt -> Halt();
	}
	SwapLock = new Lock("SwapLock");

	useFIFO = true;

	//DEBUG('3',"Swap File Initialized\n");

	//TLBLock = new Lock("TLBLock");
	nextTLBEntry = 0;
	lastProcessId = -5;
	ipt = new InvertedTranslationEntry[NumPhysPages];
	for(int i=0;i<NumPhysPages;i++)
		ipt[i].valid = false;;
	
	IPTLock = new Lock("ITPLock");
	tmpLock = new Lock("tmpLock");

	queue = new List();
}

void finalizeMMU()
{
	//DEBUG('3',"Finalize Varibles needed in Memory Management Unit\n");
	
	delete SwapFileMap;
	delete SwapFile;
	fileSystem -> Remove("Group11SwapFile");
	//delete memory;
	
	delete SwapLock;
	
	//delete TLBLock;
	
	/*for(int i=0;i<NumPhysPages;i++)
		if(ipt[i]!=NULL)
			delete ipt[i];
	*/

	delete[] ipt;
	
	delete IPTLock;
	
	delete tmpLock;

	delete queue;
}

/***************************
 *	Swap File Management   *
 ***************************/
void giveupSwap(int posId)
{
	SwapLock -> Acquire();
	DEBUG('5',"[Swap Del] Give up pos id = %d\n", posId);
	SwapFileMap -> Clear(posId);
	SwapLock -> Release();
}

//return position ID
int SaveInSwap(int physicalPage)
{
	SwapLock -> Acquire();
	
	//Assign posID
	int posId = SwapFileMap -> Find();
	if(posId == -1)
	{
		printf("FATAL ERROR : Swap File is full\n");
		return -1;
	}

	DEBUG('5',"[Swap Out] Write page #%d into swap file, pos = %d\n", physicalPage, posId);

	//Copy from Memory to Swap File
	SwapFile->WriteAt( &(machine->mainMemory[physicalPage*PageSize]), PageSize, posId*PageSize);
	
	//for(int i=0;i<PageSize;i++)
	//	memory[posId*PageSize+i] = machine->mainMemory[physicalPage*PageSize+i];


	SwapLock -> Release();

	//Return posId
	return posId;
}

void ReadFromSwap(int physicalPage, int posId)
{
	SwapLock -> Acquire();
	
	DEBUG('5',"[Swap In ] Read  page #%d from swap file, pos = %d\n", physicalPage, posId);

	SwapFile->ReadAt(&(machine->mainMemory[physicalPage*PageSize]), PageSize, posId*PageSize);
	//for(int i=0;i<PageSize;i++)
	//	machine->mainMemory[physicalPage*PageSize+i]=memory[posId*PageSize+i]; 


	
	SwapFileMap -> Clear(posId);

	SwapLock -> Release();
}

/***************************
 *	TLB Management		   *
 ***************************/
//This is called when want to make a TLB entry invalid
//the second arg denote if you want it to change dirty bit in IPT automatically
//return dirty bit any way.
bool invalidateTLB(int index, bool affectIPT)
{
	TranslationEntry* entry = & machine->tlb[index];
	
	DEBUG('3',"[Invalidate TLB]    vpn=%-3d ppn=%-3d valid=%d dirty=%d index=%d\n",entry->virtualPage, entry->physicalPage,false, entry->dirty, index);
	
	if(!entry->valid)	//if it si already invalid, skip
		return false;
	entry -> valid = false;

	if(affectIPT && entry -> dirty)//If it is dirty and valid and Can affect IPT
	{
		int ppn = entry -> physicalPage;

		InvertedTranslationEntry * IEntry = &ipt[ppn];

		if(IEntry -> virtualPage != entry -> virtualPage)	//If want to check process Id , should use lastProcessId.
		{
			printf("FATAL ERROR : TLB info doesn't match IPT info\n");
			return true;
		}

		IEntry -> dirty = true;

		DEBUG('4',"[UpdateIPT]SetDirty vpn=%-3d ppn=%-3d valid=%d dirty=%d processId=%d\n",IEntry->virtualPage, IEntry->physicalPage,IEntry->valid, IEntry->dirty, IEntry->processId);
	}
	return entry->dirty;
}

//This is called by IPT to recycle its shadow in TLB
//Will always return dirty bit
bool recycleTLB(int ppn, int vpn)
{
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	DEBUG('3',"Recyle TLB related to VPN=%d PPN=%d ",vpn,ppn);	
	bool dirty = false;
	for(int i=0;i<TLBSize;i++)
	{
		TranslationEntry * en = &(machine -> tlb[i]);
		if(!en->valid)
			continue;
		if(en->physicalPage!=ppn || en->virtualPage!=vpn)
			continue;
		
		DEBUG('3',"[one]valid=%d dirty=%d index=%d",en->valid, en->dirty,i);	

		dirty = en->dirty;
		en->valid = false;
		break;
	}
	DEBUG('3',"\n");	
	
	interrupt -> SetLevel(oldLevel);
	
	return dirty;
}

/***************************
 *	IPT Management		   *
 ***************************/
//--------Utility--------

//Generate Random number
int Random(int limit)
{
	return (int) (limit*(double)rand()/((double)R_MAX+1.0));
}

//Description: calculate storing Key in hash table.
int genKey(int vpn)
{
	int key = currentThread -> processId * 100000 + vpn;
	//DEBUG('4',"Gen Key : VPN = %d , ProcessId = %d , key = %d \n", vpn, currentThread -> processId, key);
	return key;
}

int genKey(int vpn, int processId)
{
	int key = processId * 100000 + vpn;
	//DEBUG('4',"Gen Key : VPN = %d , ProcessId = %d , key = %d \n", vpn, currentThread -> processId, key);
	return key;
}

//Description: operate hash map.
void putHash(int key, int value)
{
	hash[key]=value;
}

int getHash(int key)
{
	if(hash.count(key))	//If this key exists in hash
		return hash[key];
	return -1;			//else return -1
}
void removeHash(int key)
{
	hash.erase(key);
}


//--------IPT CORE--------

//return the physical page number (index into ipt)
//Assumption:	1)should do swap in and update TLB if necessary
//				2)Only get called when physical memory is full
//				3)Return evicted physical page number

//TODO : 2 Algorithm to evict.
int evictIPT()
{
	int ppn;
	
	if(useFIFO)
		ppn=(int)queue->Remove();
	else
		ppn=Random(NumPhysPages);

	InvertedTranslationEntry * IE = &ipt[ppn];
	/*
	if(IE==NULL)							//Rare chance that map is wrong.
	{
		ipt[ppn] = new InvertedTranslationEntry();
		DEBUG('%',"[Evict IPT] PPN %d is empty!\n",ppn);
		return ppn;
	}
	*/
	//Update TLB
	int vpn = IE->virtualPage;
	
	DEBUG('4',"[Evict IPT]Detail:  VPN=%-3d PPN=%-3d valid=%d dirty=%d ProcessID=%d\n",vpn, ppn, IE->valid, IE->dirty, IE->processId);
	
	if(!IE->valid)
	{
		printf("FATAL ERROR : Trying to evict a page while Memory is not full!");
		return ppn;
	}

	//Update PageTable
	AddrSpace * space = GetProcess(IE->processId) -> space;
	space -> pageTable[vpn].valid = false;	//Not in memory now

	//Do Swap if necessary
	//if(recycleTLB(ppn, vpn) || IE->dirty)
	//{
	recycleTLB(ppn,vpn);
	//save in swap
	int posId = SaveInSwap(ppn);
	//save posId
	space -> pageTable[vpn].inDisk = true;
	space -> pageTable[vpn].posId = posId;
	//}

	//Update IPT
	IE -> valid = false;
	removeHash(genKey(IE->virtualPage, IE->processId));

	return ppn;
}


//This is only called on demand.
//Description:	populate into IPT table
//Assumption:	assign physical page
//				assign processId
void populateIPT(int vpn, int physPage, bool isValid, bool isUse, bool isDirty, bool readOnly)
{
	//TODO: remove pre-load someday
	//int physPage = RequestMemoryPage();
	//if(physPage == -1)
	//{
	//	DEBUG('4',"Failed to populate IPT because Memory is FULL!!\n");
	//	return -1;
	//}

//TODO !!!!!!!!!!!
//What to do if IPT is pccupied??

	IPTLock -> Acquire();

	//If empty, create new entry
	/*if(ipt[physPage]==NULL)
		ipt[physPage]= new InvertedTranslationEntry();
	else*/
	if(ipt[physPage].valid)
		printf("ERROR! Trying to cover a valid entry in  populate IPT\n");

	//Set information in entry
	InvertedTranslationEntry * entry = &ipt[physPage];
	entry -> virtualPage = vpn;
	entry -> physicalPage = physPage;
	entry -> valid = isValid;
	entry -> use = isUse;
	entry -> dirty = isDirty;
	entry -> readOnly = readOnly;
	entry -> processId = currentThread -> processId; //IMPORTANT!!!!

	//Put index in hashtable to enable quick find
	putHash(genKey(vpn),physPage);
	queue->Append((void*)physPage);
	//TODO: In future, have to save evicted pages before updating IPT.
	//DEBUG('4',"[IPT Populated]: VPN=%3d physPage=%3d valid=%d use=%d dirty=%d readOnly=%d <Key=%-7d Hash[key]=%-3d>\n", vpn, physPage, isValid, isUse, isDirty, readOnly, genKey(vpn), getHash(genKey(vpn)));
	DEBUG('4',"[IPT Populated]:    VPN=%-3d PPN=%-3d valid=%d dirty=%d readOnly=%d ProcessID=%d\n", entry->virtualPage,entry->physicalPage, entry->valid, entry->dirty, entry->readOnly, entry->processId );

	IPTLock -> Release();
}
	
InvertedTranslationEntry * queryIPT(int vpn)
{
	IPTLock -> Acquire();

	int phys = getHash( genKey(vpn) );
	
	InvertedTranslationEntry * entry;

	if(phys == -1)
	{
		/*
		for(int i=0;i<NumPhysPages;i++)
		{	
			if(ipt[i]==NULL || !ipt[i]->valid)
				continue;
			if( (ipt[i]->virtualPage == vpn) && ( ipt[i]->processId == currentThread->processId) )
			{
				printf("FATAL ERROR : hash index forgot an entry in IPT!\n");
				phys = ipt[i] -> physicalPage;
				break;
			}
		}
		if(phys == -1)*/
			//On IPT Miss!!!
			phys = OnMissIPT(vpn);
			entry = &ipt[phys];
	}
	else
	{
		entry = &ipt[phys];

		if( (entry == NULL)||(!entry -> valid)||( entry->processId != currentThread->processId)||(entry->virtualPage != vpn) )
		{	
			printf("FATAL ERROR : hash index misremember an entry in IPT!\n");
			removeHash(genKey(vpn));
			phys = OnMissIPT(vpn);
			entry = &ipt[phys];
		}
		/*
		//Double Check: None of these should prompt out
		if(entry == NULL)
		{
			printf("FATAL ERROR : Retrieved IPT Entry is NULL. \n");
			IPTLock -> Release();
			return NULL;
		}
	
		if(!entry -> valid)
		{
			printf("FATAL ERROR: Retrieved IPT Entry is already INVALID\n");
			IPTLock -> Release();
			return NULL;
		}

		if( entry -> processId != currentThread -> processId)
		{
			printf("FATAL ERROR: IPT entry doesn't belong to current process \n");	//TODO
			IPTLock -> Release();
			return NULL;
		}

		if( entry -> virtualPage != vpn)
		{
			printf("FATAL ERROR: IPT entry doesn't point to target vpn \n");	//TODO
			IPTLock -> Release();
			return NULL;
		}*/
	}
	
	//DEBUG('4',"[QueryIPT]: VPN=%3d PorcessId=%2d \n", vpn, currentThread->processId);
	
	DEBUG('4',"[IPTQuery]: SUCCESS VPN=%-3d PPN=%-3d valid=%d dirty=%d readOnly=%d ProcessId=%d\n", entry->virtualPage,entry->physicalPage, entry->valid, entry->dirty,entry->readOnly, entry->processId);

	IPTLock -> Release();

	return entry;
}

/************************************
 *		Program Stub				*
 ************************************/

//This is the only Function automatically called on context switch
void TLBCleanUp()
{
	IntStatus oldLevel = interrupt -> SetLevel(IntOff);

	int processId = currentThread -> processId;
	if(lastProcessId == processId)
	{
		DEBUG('3',"Context switch between same process, skip TLB clean up\n");
	}
	else
	{
		DEBUG('3',"Clean Up TLB.....\n");
		//TODO: Remember to pass dirty bit to IPT
		for(int i=0;i<TLBSize;i++)
		{
			invalidateTLB(i,true);
			//machine -> tlb[i].valid = false;
		}
		lastProcessId = processId;
	}

	interrupt -> SetLevel(oldLevel);
}

//This is the only Fuction automatically called on Miss TLB
bool OnMissTLB(unsigned int Vaddr)
{
	tmpLock -> Acquire();

	IntStatus oldLevel = interrupt -> SetLevel(IntOff);

	int vpn = (int)(Vaddr / (unsigned int)PageSize);		//Calculate Virtual Page Number

	TranslationEntry * entry = queryIPT(vpn);				//query IPT On tlb miss
/*
	if(entry == NULL)
	{
		printf("FATAL ERROR : Query IPT FAILED. \n");
		interrupt -> SetLevel(oldLevel);
		tmpLock -> Release();
		return false;
	}
*/	
	if(machine -> tlb[nextTLBEntry].valid)					//If the TLB to be covered is valid
		invalidateTLB(nextTLBEntry,true);


	machine -> tlb[nextTLBEntry].valid = true;	
	machine -> tlb[nextTLBEntry].virtualPage = vpn;
	machine -> tlb[nextTLBEntry].physicalPage = entry->physicalPage;	
	machine -> tlb[nextTLBEntry].use = false;				//Reconsider!!!!
	machine -> tlb[nextTLBEntry].dirty = false;	
	machine -> tlb[nextTLBEntry].readOnly = entry->readOnly;
	
	DEBUG('3',"[TLB Update]:       VPN=%-3d PPN=%-3d valid=%d dirty=%d TLBIndex=%d\n", vpn, machine -> tlb[nextTLBEntry].physicalPage,	machine -> tlb[nextTLBEntry].valid,	machine -> tlb[nextTLBEntry].dirty  , nextTLBEntry);

	nextTLBEntry = (nextTLBEntry + 1) % TLBSize;

	interrupt -> SetLevel(oldLevel);
	
	tmpLock -> Release();
	return true;
}

int OnMissIPT(int vpn)
{
	IPTLock -> Acquire();
	//DEBUG('4',"[IPT MISS!]\n");

	//OnMissIPT should have restore/set data in physical memory if necessary
	int i = currentThread -> space -> OnMissIPT(vpn);
	IPTLock -> Release();
	return i;
}

//the target of recycleIPT is to recycle useless IPT entry
//needn't pop lots of errors.

//recycleIPT don't worry about memory page recycle

//recycleIPT worry about 
void recycleIPT(int vpn)
{
	IPTLock -> Acquire();
	
	int phys = getHash( genKey(vpn) );

	if(phys == -1)
	{	//no such entry in IPT, sneedn't recycle
		DEBUG('4',"[IPT Recycle]: Failed to recycle %d due to hash not exist, process=%d\n", vpn, currentThread->processId);
		IPTLock -> Release();
		return ;
	}

	//DEBUG('4',"HashMap : target physPage is %d \n", phys);
	InvertedTranslationEntry * entry = &ipt[phys];
	removeHash(genKey(vpn));									//clear hash for that vpn
	/*
	if(entry == NULL)
	{
		//no such entry in IPT, sneedn't recycle
		IPTLock -> Release();
		return ;
	}
	*/
	if(!entry -> valid)
	{
		DEBUG('4',"[IPT Recycle]: Failed to recycle %d ,already invalid,  process=%d\n", vpn, currentThread->processId);
		//this IPT is already valid, skip it
		IPTLock -> Release();
		return ;
	}

	if( entry -> processId != currentThread -> processId || entry -> virtualPage != vpn)
	{
		DEBUG('4',"[IPT Recycle]: Failed to recycle %d ,Info doesn't match,  process=%d\n", vpn, currentThread->processId);
		
		//this entry doesn;t belong to current process, skip it 
		IPTLock -> Release();
		return ;
	}
	//TODO what if it is dirty? Nothing

	DEBUG('4',"[IPT Recycle]: SUCCESS VPN=%3d PorcessId=%2d\n", vpn, currentThread->processId);
	entry -> valid = false;										//set valid to false
																//hash has been removed above
	recycleTLB(phys, vpn);										//kickout TLB

	IPTLock -> Release();
}


#endif //USE_TLB
